1. Technical Field
The present invention relates generally to a communication systems and in particular to a method and apparatus for routing data within the communications system. Still more particularly, the present invention relates to a switching system employed for routing cells from a source to a destination in a communications system.
2. Description of the Related Art
Factors driving the need for broadband communications arise from changing user needs and demands. Previously, public network needs were driven by telephoning, voice data. Data traffic has grown slowly until recently. With the lower cost in telecommunications and the higher increase in processing power of computers, the numbers of users accessing communications networks has increased. The needs of these users include, for example, video telephone, low cost video conferencing, imaging, high definition television (HDTV), and other applications requiring multimedia data transfers. Multimedia combines different forms of media in the communication of information between a user and a data processing system, such as a personal computer. A multimedia application is an application that uses different forms of communications within a single application. Multimedia applications may, for example, communicate data to a user on a computer via audio, text, and video simultaneously. Such multimedia applications are usually bit intensive, real time, and very demanding on communications networks. A number of definitions have been given for broadband service. One example is the International Telecommunications Union (ITU, formerly known as CCITT), which defines broadband service as a service requiring transmission channels capable of supporting rates greater than 1.5 Mbps or a primary rate in ISDN or T1 or DS1 in digital terminology. A broadband integrated services digital network (BISDN) technology framework involves asynchronous transfer mode (ATM) as a protocol for coordinating information flow at a source and destination node. For terrestrial networks, synchronous optical network (SONET), a standard for fiber optical transmission mediums form the backbone technology for BISDN. More information on broadband communications can be found in Kumar, Broadband Communications: A Professional's Guide to (ATM) Frame Relay, SMDS, SONET, and BISDN, McGraw-Hill, Inc., New York, (1995).
The progress in fiber optic and network technologies have made BISDN a commercial reality and has made possible sophisticated computer applications, such as the transmission of video, voice, and other data over computer networks. ATM is the most common switching technique used by broadband networks to integrate a variety of multirate services, ranging from high speed video services and computer communications to low speed voice services, into a single high speed network. Currently, the ATM standard defined by ITU specifies fixed packet sizes (cells) consisting of 5 bytes in a control field and 48 bytes in a data field and supports line speeds of up to 150 Mbps, 600 Mbps, or above. ATM networks are packet-oriented, in which information is packetized, carried in fixed length packets, and transmitted in a slot by slot fashion. Most integrated services provided by BISDN falls into two major categories. In the first category, circuit emulation type, also called connection oriented, requires reserving the bandwidth for the whole duration of the connection because extremely low cell loss rates, such as less than 1e-1, is crucial. In the second category, the connectionless type, the bandwidth requirement is unpredictable and bursty, such as in intercomputer data communication, but a certain degree of cell loss is tolerable, such as less than 1e-6. In networks that provide both types of services, it is very common and desirable to assign higher priority to the cells of connection-oriented services than to the cells of connectionless services.
To meet high speed transmission demands, ATM employs a hardware-based fast packet switching technique that allows cells to be self-routed from input ports through an interconnection network to output ports by using the destination information stored in cell headers. Carrying large amounts of information over long distances with the help of high bandwidth satellites or fiber optics is straight forward, but the switching of high-speed packet flows is a challenging task.
The design of BISDN and ATM switches is made more difficult by the requirement that customer expectations be met and the network be used efficiently. One way to satisfy customer expectations is for the switches to ensure that the quality of service (QoS) parameter values for the multimedia services are not exceeded. A further complication of switch design is that the switches are required to have a high degree of fault-tolerance. Modern satellite systems, such as Teledesic and Advanced Satcom, have ATM switches on board the satellites. ATM networks and these types of satellites carry a large volume of integrated multimedia traffic. As a result, a failure in the switches can be catastrophic for a large number of users. Additionally, networks including satellite switches impose other complications on switch design. If the ATM switch is to be implemented on board the satellite, then the ATM switch must be as small as possible and must be implemented in technologies that consume as little power as possible.
Output conflicts and internal conflicts are two kinds of conflicts that may occur within a switching system. When several cells attempt to reach the same output at the same time, an output conflict occurs. On the other hand, an internal conflict occurs whenever two or more cells simultaneously try to use the same internal link in the communications network. Output and internal conflicts cause cells to be discarded.
Several buffer schemes have been proposed to reduce the conflicts and maintain packet loss within a desired range. These buffer schemes can be classified into three categories: input queueing, central queueing, and output queueing. For a network of size N, if the switch fabric can run N times as fast as the input and output links (i.e., with a speed-up factor of "N"), all of the arriving cells in the current time slot can be routed to their destinations before the next time slot. Thus, in the worst case, even if all the N incoming cells may request the same output, only output queues are needed. On the other hand, if a switch fabric can run only as fast as the input and output links, then only one cell per output is allowed during the time slot, and input queues are required to store the rest of the cells addressed for the same output.
Buffers are usually required in the switch elements of the switch fabric to resolve internal link usage conflicts. A Banyan switch, also called a "single path switching matrix", is a blocking network and requires internal buffers, but can become nonblocking if the incoming cells have been presorted by a batcher sorting network. Input queueing suffers from low-performance and internal queueing, also called central queueing, requires expensive and fast internal links within a switch. Output queueing has the best performance among the three, but requires the highest hardware complexity of the schemes.
Space switching has the merit of allowing high speed operation and is most appropriate for BISDN and ATM networks. According to hardware complexity, space switching can be further divided into four subcategories. (a) N.sup.2 disjoint path switching, (b) crossbar switching, (c) Banyan-based switching, and (d) shared-memory switching. Switches in the first three categories have large switch sizes and are expensive. Additionally, the performance varies with the network size.
With respect to shared memory switching, shared memory buffer management schemes, as mentioned above, includes input queueing, central queueing, and output queueing. Among all buffer management schemes, the simplest scheme is input queueing with first-and-first-out (FIFO) discipline. Head-of-line (HOL) blocking, reduces the maximum output in this queueing system. HOL blocking may exist in FIFO queues in input portions of switches. HOL blocking can reduce the throughput of switches because once the front cell in an input queue loses the contention for an output port, the cell will remain in the input queue and wait for a retry in the next time slot. Thus, the cell blocks other cells in the queue from being served even though their destination outputs may be idled. Several input queueing schemes employ a window service mechanism. Under this mechanism, those input links of these first cells do not win the output contentions can have their second cells contend for access to any idol output port. This procedure is repeated for the first W cells (window size) of each queue. The window size approach requires very complicated control hardware, but still only allows one cell from an input queue in a time slot to access the output ports. Thus, the resulting performance/cost ratio is poor.
In central queueing, a switch can run N times as fast as the input and output links (i.e., with a speed up factor of N) so that all the arriving cells in the current time slot can be routed to the destinations before the next time slot. Existing output queueing switches presently available require a large amount of hardware, have a large end to end delay, do not tolerate faults, or require expensive implementation technology.
Thus, it would be advantageous to have an approved switch for routing cells without the drawbacks mentioned for the various shared memory buffer management schemes described above. It would be advantageous to have an ATM switch that satisfies quality of standard requirements for various multi-media services but with smaller hardware cost than comparable existing ATM switches. It would also be advantageous if such a switch could be implemented using inexpensive technology consuming little power, scalable to handling various amount of traffic, and performance that is insensitive to the communications network size.